⟸ Go Back ⟸

Exercise 2 (Homework 2).

(regular languages, complement, minimization of DFAs)

Complement of a regular language is regular

Exchanging final and non-final states in a DFA A produces a new DFA that recognizes the complement of the language recognized by A.

1. Show that L=\{aax\mid x\in\{a,b\}^*\} is a regular language. Construct the minimum DFAs recognizing L and \overline{L}.

2. Show that L=\{w \in \{a,b\}^* \mid |w|\in 3\mathbb N+1\} is a regular language. Construct the minimum DFAs recognizing L and \overline{L}.

3. Show that L=\{w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 3\mathbb N\} is a regular language. Construct the minimum DFAs recognizing L and \overline{L}.

4. Given as input a DFA A, what is the cost of constructing a DFA for \overline{L(A)}?

5. If we started with a minimum DFA, is the obtained DFA for the complement minimum?

6. Does exchanging final states and non-final states in an NFA A produce an NFA recognizing the complement of the language recognized by A?